package com.yangzhe.algorithm.c021;

// 归并排序，acm练习风格
// 测试链接 : https://www.luogu.com.cn/problem/P1177
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

import java.io.*;

public class Code01_MergeSort_Acm {
    /**
     * 说明/提示
     * 对于 20% 的数据，有 1≤N≤10 ^ 3；
     * 对于 100% 的数据，有 1≤N≤10 ^ 5，1≤ai ≤10 ^ 9。
     */
    public static final int MAX_LENGTH = 10 ^ 9 + 1;

    public static int n;

    public static int[] nums = new int[MAX_LENGTH];

    /**
     * 辅助数组，长度等于题目的数组长度
     */
    public static int[] help = new int[MAX_LENGTH];

    public static void main(String[] args) throws IOException {
        try (InputStreamReader inputStreamReader = new InputStreamReader(System.in);
             BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
        ) {
            StreamTokenizer tokenizer = new StreamTokenizer(bufferedReader);
            tokenizer.nextToken();
            n = (int) tokenizer.nval;

            for (int i = 0; i < n; i++) {
                tokenizer.nextToken();
                nums[i] = (int) tokenizer.nval;
            }
        }

        mergeSort1(0, n - 1);

        try (OutputStreamWriter outputStreamWriter = new OutputStreamWriter(System.out);
             PrintWriter printWriter = new PrintWriter(outputStreamWriter)
        ) {
            for (int i = 0; i < n; i++) {
                printWriter.print(nums[i] + "");
            }

            printWriter.flush();
        }
    }

    // 归并排序递归版
    // 假设l...r一共n个数
    // T(n) = 2 * T(n/2) + O(n)
    // a = 2, b = 2, c = 1
    // 根据master公式，时间复杂度O(n * logn)
    // 空间复杂度O(n)
    public static void mergeSort1(int l, int r) {
        // base case，左下标、右下标一致，则直接返回，因为一个数字肯定是有序的
        if (l == r) {
            return;
        }

        // 去中间位置
        int m = (l + r) / 2;

        // 让左侧都有序
        mergeSort1(l, m);
        // 让右侧都有序
        mergeSort1(m + 1, r);
        // 将左侧和右侧数组合并
        merge(l, m, r);
    }

    // 归并排序非递归版
    // 时间复杂度O(n * logn)
    // 空间复杂度O(n)
    public static void mergeSort2() {

    }

    // l....r 一共有n个数
    // O(n)
    public static void merge(int l, int m, int r) {
        int lIndex = l;
        int rIndex = m + 1;
        int helpIndex = 0;
        // 将左右两边合并到help数组中
        while (lIndex <= m && rIndex <= r) {
            // 哪边小copy哪边到help数组中
            if (nums[lIndex] < nums[rIndex]) {
                help[helpIndex] = nums[lIndex++];
            } else {
                help[helpIndex] = nums[rIndex++];
            }
            helpIndex++;
        }

        // 左右两边总会有一边会剩余
        // 如果左边剩余，把左边剩余的全部copy到help数组中
        while (lIndex <= m) {
            help[helpIndex++] = nums[lIndex++];
        }

        // 如果右边剩余，把右边剩余的全部copy到help数组中
        while (rIndex <= r){
            help[helpIndex++] = nums[rIndex++];
        }

        // 将help数组覆盖到原数组原来的位置中
        for (int i = 0; i < helpIndex; i++) {
            nums[l + i] = help[i];
        }
    }
}